package leetcode.code1997;

import leetcode.IDebug;
import leetcode.helper.H;
import leetcode.helper.tree.TreeNode;

// 涉及mod (int) 1e9 + 7 减法要加一个mod
// mod问题哪怕是最后+1也要补一次mod
public class Solution3 implements IDebug {

	int mod = (int) 1e9 + 7;

	public int firstDayBeenInAllRooms(int[] nextVisit) {
		int n = nextVisit.length;
		long[] d1 = new long[n];
		d1[0] = 0;
		for (int i = 1; i < n; i++) {
			d1[i] = ((d1[i - 1] + 1) * 2 + mod - d1[nextVisit[i - 1]]) % mod;
		}
		return (int) d1[n - 1];
	}

	@Override
	public void debug4() {
		H.compare(0, this.firstDayBeenInAllRooms(H.str2array3(
				"[0,0,0,0,2,2,1,2,3,8,9,5,1,6,8,5,10,5,18,2,15,7,22,4,6,10,19,16,3,25,12,28,1,27,25,25,35,16,7,23,37,8,28,8,18,41,36,29]")));
		H.compare(86417750, this.firstDayBeenInAllRooms(H.str2array3(
				"[0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48]")));
		H.compare(6, this.firstDayBeenInAllRooms(H.str2array3("[0,0,2]")));
		H.compare(6, this.firstDayBeenInAllRooms(H.str2array3("[0,1,2,0]")));
		H.compare(2, this.firstDayBeenInAllRooms(H.str2array3("[0,0]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		TreeNode tn = new TreeNode(4);
//		tn.left = new TreeNode(2);
//		tn.right = new TreeNode(5);
//		tn.left.left = new TreeNode(1);
//		tn.left.right = new TreeNode(3);
//		m(tn);
//
//		TreeNode tn1 = new TreeNode(2);
//		tn1.left = new TreeNode(1);
//		tn1.right = new TreeNode(4);
//		tn1.right.left = new TreeNode(3);
//		tn1.right.right = new TreeNode(5);
//		m(tn1);
	}

	public static void m(TreeNode root) {
		if (root == null) {
			return;
		}
		m(root.left);
		System.out.println(root.val);
		m(root.right);
	}

}
